package com.longge;

public class ShipWithinDays {


    public int shipWithinDays(int[] weights, int days) {

        int left = 0, right = 1;
        for (int weight : weights) {
            left = Math.max(weight, left);
            right += weight;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (f(weights, mid) == days) {
                right = mid;
            } else if (f(weights, mid) < days) {
                right = mid;
            } else if (f(weights, mid) > days) {
                left = mid + 1;
            }
        }
        return left;

    }

    int f(int[] weights, int x) {
        int day = 1;
        int count = x, i = 0;
        while (i < weights.length) {
            count -= weights[i++];
            if (count < 0) {
                i--;
                count = x;
                day++;
            }

        }
        return day;
    }

    public static void main(String[] args) {
        int f = new ShipWithinDays().f(new int[]{1, 2, 3, 4, 5, 5, 7, 8, 9, 10}, 15);
        System.out.println(f);
    }
}
